package labuladong.滑动窗口;

import org.omg.CORBA.INTERNAL;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Demo01 {
    public static void main(String[] args) {
        String t = "aabb";
        String s = "eidboaaboo";
        boolean flag = checkInclsion(t, s);
        System.out.println(flag);
    }

    public static boolean checkInclsion(String t, String s) {
        int left = 0, right = 0, valid = 0;
        char[] tArray = t.toCharArray();
        char[] sArray = s.toCharArray();
        Map<Character, Integer> need = new HashMap<Character, Integer>();
        Map<Character, Integer> window = new HashMap<Character, Integer>();

        for(Character c:tArray) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        while (right < sArray.length) {
            // 依次取出每个字符
            char c = sArray[right];
            // 右移
            right ++;
            // 判断取出的字符是否出现在目标字符串里
            if (need.containsKey(c)) {
                // 出现，将字符计入窗口
                window.put(c, window.getOrDefault(c, 0)+1);
                // 判断窗口里所含才c字符的value是否等于need中的c字符的value
                // value值相同，valid +1
                if (window.get(c) == need.get(c)) {
                    valid ++;
                }
            }

            // 如果valid等于need的长度，说明窗口内可能含有解
            while (right - left >= need.size()) {
                // 若valid等于need的长度
                if (valid == need.size()) {
                    return true;
                }
                // valid不等于need的长度，left右移
                char d = sArray[left];
                left ++;
                // 进行窗口内的一系列数据的更新
                if (need.containsKey(d)) {
                    // 如果窗口内包含满足条件的d，则valid减1
                    if (window.get(d) == need.get(d)) {
                        valid --;
                    }
                    // 窗口window里对应的key的value减1
                    window.put(d, window.get(d) - 1);
                    // 如果窗口内的d的value为0，则从window中移除
                    if (window.get(d) == 0) {
                        window.remove(d);
                    }
                }
            }
        }
        return false;
    }
}
